package com.xinxin.leetcode.problem653;

import com.xinxin.leetcode.common.CommonUtil;
import com.xinxin.leetcode.common.TreeNode;
import com.xinxin.leetcode.common.TreeUtil;

import java.util.HashSet;

/**
 * @author ShiXinXin
 * @date 2020-02-16 0:17
 */
public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        HashSet<Integer> set = new HashSet<>();
        return preOrder(root, set, k);
    }

    public boolean preOrder(TreeNode root, HashSet<Integer> set, int k) {
        if (root == null) {
            return false;
        }
        if (set.contains(k - root.val)) {
            return true;
        }
        set.add(root.val);
        return preOrder(root.left, set, k) || preOrder(root.right, set, k);
    }

    public static void main(String[] args) {
        TreeNode root = TreeUtil.createTree(CommonUtil.createArr(5, 3, 2, 0, 0, 4, 0, 0, 6, 0, 7, 0, 0));
        int target = 9;
        System.out.println(new Solution().findTarget(root, target));
    }
}
